using System;
using System.Numerics;
using System.Text;

namespace BinIntegerMultiplication
{
    public class MyBigInteger
    {
        private string digits; 

        private static readonly MyBigInteger zero = new MyBigInteger("0");

        public MyBigInteger(string digits)
        {
            this.digits = digits;
        }

        public MyBigInteger(BigInteger bigInteger)
            : this(bigInteger.ToString())
        {
        }

        private MyBigInteger(string source, int start, int len)
        {
            digits = source.Substring(start, len);
        }

        public static MyBigInteger operator *(MyBigInteger first, MyBigInteger second)
        {
            var len1 = first.digits.Length;
            int len2 = second.digits.Length; 
            
            if (len1 <= 0 || len2 <= 0) 
                return zero;

            var n = Math.Max(len1, len2);

            if (n <= 1) 
                return new MyBigInteger(Digit(first.digits, 0) * Digit(second.digits, 0));

            int m = n / 2;

            var a = new MyBigInteger(first.digits, 0, len1 - m);
            var b = new MyBigInteger(first.digits, len1 - m, m);
            var c = new MyBigInteger(second.digits, 0, len2 - m);
            var d = new MyBigInteger(second.digits, len2 - m, m);

            var ac = a * c;
            var ad = a * d;
            var bc = b * c;
            var bd = b * d;

            return ac.Pow10(2 * m) + (ad + bc).Pow10(m) + bd;             
        }

        private MyBigInteger Pow10(int n)
        {
            if (Equals(zero))
            {
                return zero;
            }

            digits += new string('0', n);

            return this;
        }

        public static implicit operator string(MyBigInteger value)
        {
            return value.ToString();
        }

        public static explicit operator BigInteger(MyBigInteger value)
        {
            return BigInteger.Parse(value);
        }

        public static explicit operator MyBigInteger(BigInteger value)
        {
            return new MyBigInteger(value);
        }

        public static MyBigInteger operator +(MyBigInteger first, MyBigInteger second)
        {
            var len1 = first.digits.Length;
            int len2 = second.digits.Length;

            if (len1 <= 0 || len2 <= 0)
                return zero;

            var n = Math.Max(len1, len2);

            if (n <= 1)
                return new MyBigInteger(Digit(first.digits, 0) + Digit(second.digits, 0));

            var sb = new StringBuilder();
            var carry = 0;

            for (int i = 0; i < n; ++i)
            {
                var temp = Digit(first.digits, len1 - i - 1) + Digit(second.digits, len2 - i - 1) + carry;

                var unit = temp % 10;
                carry = temp / 10;

                sb.Insert(0, (char)(unit + '0'));
            }

            if (carry > 0)
                sb.Insert(0, (char)(carry + '0'));                

            return new MyBigInteger(sb.ToString().TrimStart('0'));
        }

        private static int Digit(string digits, int pos)
        {            
            return pos >= 0 ? digits[pos] - '0' : 0;
        }

        public override bool Equals(object obj)
        {
            return ToString() == obj.ToString();
        }

        public override string ToString()
        {
            return digits == "" ? "0" : digits;
        }
    }
}